\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}
\mode<article>{\usepackage{fullpage}}

\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}

\title{Lecture Eight -- Recursion}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}
\mode<all>{\bibliographystyle{abbrvnat}}


\section{Recursion}
\subsection{A Brief Overview}
A recursive function is one that calls itself.  However, the function
must be constructed such that it exits at some point (lest we have an
infinite loop).  Though recursion seems to be downplayed in this day
and age (in fact, some would argue it is not properly implemented in
Java), I feel it is a topic that, once understood, makes everyone a
better programmer.  Also realize that even in our pro-iteration world,
some problems are only tractable through recursive solutions.

We've already seen recursive acronyms like GNU (GNU is Not Unix);
silly as that is, it does capture the general idea.

\subsection{Recursive List Operations}
Languages like Lisp and Scheme not only rely on recursion, but also on
lists.  
\href{http://repository.thatmattbone.com/comp271/cs271/src/cs271/examples/recursion/Lists.java}{Here}
we look at some Lispy list problems in Java.  Pay particular
attention to the \texttt{min} method.

\subsection{Recursion in Erlang}
Some languages place a larger emphasis on recursion than Java.  Many
of these languages ascribe to the functional programming paradigm.  As
an example, let's look at recursion in \href{http://erlang.org}{Erlang}.

\begin{verbatim}
-module(tut1).
-export([fib/1, fac/1]).

fac(1) ->
  1;
fac(N) ->
  N*fac(N-1).

fib(0) ->
   1;
fib(1) ->
   1;
fib(2) ->
   1;
fib(N) ->
  fib(N-2) + fib(N-1).
\end{verbatim}
Notice that there are no explicitly if statements as in our Java
examples.  This is because the special language syntax takes care of
the base cases.  For instance \texttt{fac(1)} definition is the base
case for finding factorials recursively, and it is explicitly defined.
However, the \texttt{fac(N)} definition provides the code for all
other cases, and, in this instance, calls the \texttt{fac} function
recursively.

Example also available
\href{http://repository.thatmattbone.com/comp271/cs271/src/cs271/examples/recursion/recurse.erl}
{here}.

\subsection{Towers of Hanoi}
The towers of Hanoi is a classic game whose solution can be found
recursively.  A nice simulation is available
\href{http://www.mazeworks.com/hanoi/index.htm}{here}. As usual,
\href{http://en.wikipedia.org/wiki/Tower_of_Hanoi}{wikipedia} provides
some nice code and commentary, too.

The key thing to take away from the towers of Hanoi is that we've
solved the problem by reducing it.  Looking back at our previous
examples, we see that we've done this all along.
\section{Tail Recursion}

  \begin{quote}
  \mode<presentation>{\frametitle{Recursion According to SICP}}
    most implementations of common languages (including Ada, Pascal,
    and C) are designed in such a way that the interpretation of any
    recursive procedure consumes an amount of memory that grows with the
    number of procedure calls, even when the process described is, in
    principle, iterative. As a consequence, these languages can describe
    iterative processes only by resorting to special-purpose ``looping
    constructs'' such as \texttt{do}, \texttt{repeat}, \texttt{until},
    \texttt{for}, and \texttt{while}. The implementation of Scheme we
    shall consider in chapter 5 does not share this defect.
\end{quote}\cite{SICP:1996}

\subsection{Recursive Factorial w/Tail Recursion}
Remember that we have to 'backtrack' when we recurse.  However, what
if the recursion is the last thing we do?  Then we do not need to
'back track'.  This is called tail recursion and some compilers can
optimize for it (javac does not).

\begin{lstlisting}
  public class Exponential {
    public static int exp(int n) {
      return exp(n,1);
    }
  
    //tail recursive:
    public static int exp(int n, int current) {
      if(n<1)
        return current;
      else
        return exp(n-1, 2*current);
    }
  }
\end{lstlisting}

\subsection{Misc Links}
\begin{itemize}
  \item \href{http://www.cs.luc.edu/~anh/e271/12/recursion.html}{Dr. Harrington's Recursion Problems}
  \item \href{http://en.wikipedia.org/wiki/Tail_recursion}{Tail Recursion} A very nice wikipedia article.
\end{itemize}

\mode<all>{\bibliography{sources}}

\end{document}
